package cn.datastruct.Algorithm;

import cn.datastruct.six.BinarySearch;

public class BinarySearchDemo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 5, 7, 10, 21, 36};
        System.out.println(BinarySearch(arr,36));
    }

    /**
     * 思路：
     * int left,标记左边的起始下标
     * int mid,标记中间边下标
     * int right,标记右边下标
     * 1.如果target > arr[mid],则从mid + 1,right
     * 2.如果target < arr[mid],则从left,mid - 1
     * 3.如果target = arr[mid],则从返回mid
     * 4.重复1.2.3
     * 5.如果left > right,返回 -1
     *  返回需要查找的下标，没有就返回-1
     * @param arr 数组
     * @param target 目标数
     * @return
     */
    public static int BinarySearch(int[] arr, int target){
        int left = 0;//左边下标
        int right = arr.length - 1;//右边下标
        int mid;//中间下标
        while(left <= right){
            mid = (left + right) / 2;
            if(target == arr[mid]){//表示找到
                return mid;
            }else if(target > arr[mid]){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return -1;
    }
}
